# 寻找整数(好题)


def find_int():
    """
    显然可以知道该数是11*17=187的倍数，如果遍历所有条件得到该题的解2022040920220409，10^16数量级，以187为步长去遍历需要遍历计算10^16//187次，
    如果把步长的数量级加大，遍历的次数就会减少，从而用时更短。
    获取更大的步长的方法：若选定一部分条件，如下面注释的部分，这样得到的解虽然有很多个，但是题目的解是在这部分解的集合中，选定两个这样的解相减得到步长，
    可以看到这个步长的数量级是10^10次方，且从这个集合的一个解出发，能够快速得到问题解。
    注释部分选取4个条件能够在2秒内解开问题，应该算暴力中比较快的。
    """

    # 找到一个减少了很多约束的解的集合
    res_list = []
    for i in range(187, int(10e10), 187):
        if i % 10 == 9 and i % 23 == 15 and i % 27 == 20 and i % 31 == 27 and i % 37 == 22 and i % 41 == 1:
            res_list.append(i)
    print(res_list)

    step = res_list[1] - res_list[0]  # 使用两个解的差作为步长
    for i in range(res_list[1], int(1e17), step):  # 使用较大的数字作为起点
        if i % 10 == 9 and i % 12 == 5 and i % 13 == 10 and i % 14 == 11 and i % 15 == 14 and i % 16 == 9 and \
                i % 18 == 11 and i % 19 == 18 and i % 20 == 9 and i % 21 == 11 and i % 22 == 11 and i % 23 == 15 and \
                i % 24 == 17 and i % 25 == 9 and i % 26 == 23 and i % 27 == 20 and i % 28 == 25 and i % 29 == 16 and \
                i % 30 == 29 and i % 31 == 27 and i % 32 == 25 and i % 37 == 22 and i % 41 == 1 and i % 49 == 46:
            return i


def find_int_china_rem():
    """中国剩余定理
    一个正整数除3余2, 除5余3, 除7余2, 求这个整数为几?
    那么假设该数位x, x % 3 = 2 并且 x % 7 = 2
    也就是 (x - 2) % 3 = 0 并且 (x - 2) % 7 = 0
    所以 x 一定是 21 的倍数再加2.
    那我们可以尝试列举所有的可能的x: [2, 23, 44, 65, 86, 107, 128, ....]
    可以看到, 23 和 128 都满足这个条件, 那么下一个符合条件的数字是几呢?
    我们用 128 - 23 = 105, 而巧合的是 3 * 5 * 7 = 105
    我们验证 128 + 105 = 233, 符合条件
    实际上, 每个符合条件的答案的步长为 step = lcm(3, 5, 7)
    """


if __name__ == '__main__':
    print(find_int())
